import com.sun.prism.impl.shape.BasicRoundRectRep;
import jdk.internal.org.objectweb.asm.tree.MultiANewArrayInsnNode;

import javax.swing.*;
import java.util.Stack;

public class Sort {

    /*直接插入排序*/
    public static void insertSort(int[] array){
        for (int i=1;i<array.length;i++){
            int tmp=array[i];
            int j = i-1;
            for (; j >=0 ; j--) {
                if(array[j]>tmp){
                    array[j+1]=array[j];
                }else{
                    break;
                }

            }
            array[j+1]=tmp;

        }
    }


    public static void insertSort1(int[] array,int start,int end){
        for (int i=start+1;i<=end;i++){
            int tmp=array[i];
            int j = i-1;
            for (; j >=0 ; j--) {
                if(array[j]>tmp){
                    array[j+1]=array[j];
                }else{
                    break;
                }

            }
            array[j+1]=tmp;

        }
    }
    /*
    * 希尔排序*/
    public static void shellSort(int[] array){

        int gap=array.length;
        //预排序
        while (gap>1){
            gap=gap/2;//分量变化
            shell(array,gap);//对每组进行排序
        }

    }
    private  static void shell(int[] array,int gap){

        for (int i =gap ; i <array.length ; i++) {
            int tmp=array[i];
            int j=i-gap;
            for (;  j>=0 ; j-=gap) {
                if (array[j]>tmp){
                    array[j+gap]=array[j];
                }
                else {
                    break;
                }
            }
            array[j+gap]=tmp;

        }

    }



    public static void swap(int[] array,int i,int j){
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }

    /*选择排序
     * （o(N^2)）
     * */

    public static void selectSort(int[] array){


        for (int i = 0; i < array.length; i++) {
            int minIndex=i;
            int j=i+1;
            for (; j < array.length; j++) {

                if(array[j]<array[minIndex]){
                    minIndex=j;

                }
            }
            swap(array,i,minIndex);
        }
    }
    /*
    * 冒泡排序*/
    public static void bubbleSort(int[] array){

        for (int i = 0; i < array.length; i++) {
            boolean len=false;
            for (int j = 0; j < array.length-i-1; j++) {
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                    len=true;

                }
            }
            if(len==false){
                return;
            }
        }
    }


    /*
    * 快排*/
    public static void quickSort(int[] array){
        quick(array,0,array.length-1);


    }
    public static void quick(int[] array,int start,int end){

        if(start>=end){
            return;
        }

        if(end-start+1<10){
            insertSort1(array,start,end);
        }


        int index=middleNum(array,start,end);//三数取中
            swap(array,start,index);
        int pivot=partitionhor(array,start,end);//基准
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);

    }

    public static int middleNum(int[] array,int left,int right) {

        int mid = left + ((right - left) >> 1);
        if (array[left] < array[right]) {
            if (array[left] > array[mid]) {
                return left;
            } else if (array[right] < array[mid]) {
                return right;
            } else {
                return mid;
            }
        } else {
            if (array[right] < array[mid]) {
                return right;
            } else if (array[left] > array[mid]) {
                return left;
            } else {
                return mid;
            }

        }
    }
    public static int partitionhor(int[] array,int left,int right){

        int tmp=array[left];//基准

        int i=left;

        while(left<right){

            while (left<right && array[right]>=tmp){
                right--;

            }

            while(left<right && array[left]<=tmp){
                left++;
            }

            swap(array,left,right);//组内数据交换

        }

        swap(array,i,left);//基准和中间位置交换


        return left;
    }

    //挖坑法

    public static int partition(int[] array,int left,int right){

        int tmp=array[left];

        while (left<right){
            while(left<right&& array[right]>=tmp){
                right--;
            }
            array[left]=array[right];
            while (left<right && array[left]<=tmp){
                left++;
            }
            array[right]=array[left];
        }

        array[left]=tmp;
        return left;

    }

    //非递归快排
    public static void quickSortNOr(int[] array){
        int left=0;
        int right=array.length-1;
        int pivot=partitionhor(array,left,right);

        Stack<Integer> stack=new Stack<>();
        if(pivot-1>left){
            stack.push(left);
            stack.push(pivot-1);
        }
        if(pivot+1<right){
            stack.push(pivot+1);
            stack.push(right);
        }
        stack.push(left);
        stack.push(pivot-1);

        stack.push(pivot+1);
        stack.push(right);
        while(!stack.isEmpty()){

            int ri=stack.pop();
            int le=stack.pop();
           int piv= partitionhor(array,le,ri);
            if(piv-1>le){
                stack.push(le);
                stack.push(piv-1);
            }
            if(piv+1<ri){
                stack.push(piv+1);
                stack.push(ri);
            }

        }



    }

    //归并
    public static void mergeSort(int[] array){
        mergeFunc(array,0,array.length-1);
    }

    public static void mergeFunc(int[] array,int left,int right){
        if(left>=right){
            return;
        }
        //分开
        int mid=left+((right-left)>>1);

        mergeFunc(array,left,mid);
        mergeFunc(array,mid+1,right);
        //合并
        merge(array,left,right,mid);
    }

    //归并非递归
    public static void merge(int[] array,int left,int right,int mid){

        int[] tmpArray=new int[right-left+1];

        int s1=left;
        int s2=mid+1;
        int e1=mid;
        int e2=right;
        int k=0;
        while (s1<=e1&&s2<=e2){
            if(array[s1]<=array[s2]){
                tmpArray[k++]=array[s1++];
            }else {
                tmpArray[k++]=array[s2++];
            }
        }
        //看那个还有数据 把没有拷贝完的数据放进去

        while (s1<=e1){
            tmpArray[k++]=array[s1++];

        }
        while (s2<=e2){
            tmpArray[k++]=array[s2++];

        }
        //合并原数组
        for (int i = 0; i <=right-left ; i++) {
            array[i+left]=tmpArray[i];
        }


    }

    public static void main(String[] args) {
        int[] array={9,6,5,2,1};
        Sort.mergeSort(array);
    }
    public static void main3(String[] args) {
        int[] array={9,6,5,2,1};
        Sort.quickSort(array);

    }
    public static void main2(String[] args) {
        int[] array={9,6,5,2,1};

        Sort.quickSort(array);


    }
    public static void main1(String[] args) {
        int[] array={9,6,5,2,1};
        Sort sort=new Sort();
/*        sort.insertSort(array);*/
        Sort.shellSort(array);
    }


}
